package problem25_Reverse_Nodes_in_kGroup;

public class MySolution {
	public class ListNode {
		int val;
		ListNode next;

		ListNode(int x) {
			val = x;
		}
		
		public String toString(){
			StringBuffer sb=new StringBuffer();
			sb.append("[");
			ListNode head=this;
			while(head!=null){
				sb.append(head.val+(head.next==null?"":","));
				head=head.next;
			}
			sb.append("]");
			return sb.toString();
		}
	}
	
	public ListNode reverseKGroup(ListNode head, int k) {
		if(head==null) return null;
		if(k==0||k==1) return head;
        ListNode dummy=new ListNode(-1);
        dummy.next=head;
        ListNode pre=dummy;
        while(true){
        	ListNode counter=pre;   
        	for(int i=0;i<k;i++){
               	if(counter.next==null){
               		return dummy.next;
               	}
               	counter=counter.next;
            }
        	ListNode tail=reverseAndReturnTail(pre,k);
        	pre=tail;
        }
	}
	
	private ListNode reverseAndReturnTail(ListNode pre,int k){
		ListNode head=pre.next;
		for(int i=0;i<k-1;i++){
			ListNode currHead=pre.next;
			pre.next=head.next;
			head.next=head.next.next;
			pre.next.next=currHead;
		}
		return head;
	}
	
	public static void main(String[] args){
		MySolution s=new MySolution();
		ListNode node1= s.new ListNode(1);
		ListNode node2= s.new ListNode(2);
		ListNode node3= s.new ListNode(3);
		node1.next=node2;
		node2.next=node3;
		ListNode head=s.reverseKGroup(node1, 2);
		System.out.print(head);
	}
}
